package com.liufei.class08;

import com.liufei.class02.Code03_Comp;

import java.util.Arrays;
import java.util.Stack;

public class Code03_PartitionAndQuickSort {

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void splitNum1(int[] arr) {
        int lessEqual = -1;
        int index = 0;
        int N = arr.length;
        while (index < N) {
            if (arr[index] <= arr[N - 1]) {
//                swap(arr, index, lessEqual + 1);
//                lessEqual++;
//                index++;
                swap(arr, index++, ++lessEqual);
            } else {
                index++;
            }
        }
    }

    public static void splitNum2(int[] arr) {
        int lessEqual = -1;
        int index = 0;
        int N = arr.length;
        int moreR = N - 1;
        while (index < moreR) {
            if (arr[index] < arr[N - 1]) {
                swap(arr, index++, ++lessEqual);
            } else if (arr[index] > arr[N - 1]) {
                swap(arr, index, --moreR);
            } else {
                // 相等的时候，index直接 ++
                index++;
            }
        }
        // 最后别忘记交换
        swap(arr, moreR, N - 1);
    }


    public static int[] partition(int[] arr, int L, int R) {
        int lessR = L - 1;
        int index = L;
        int moreL = R;
        while (index < moreL) {
            if (arr[index] < arr[R]) {
                swap(arr, index++, ++lessR);
            } else if (arr[index] > arr[R]) {
                swap(arr, index, --moreL);
            } else {
                // 相等的时候，index直接 ++
                index++;
            }
        }
        // 最后别忘记交换
        swap(arr, moreL, R);
        return new int[]{lessR + 1, moreL};
    }

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] equalE = partition(arr, L, R);
        process(arr, L, equalE[0] - 1);
        process(arr, equalE[1] + 1, R);
    }


    public static void quickSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[] {0, arr.length - 1});
        while (!stack.isEmpty()) {
            int[] cur = stack.pop();
            int[] equals = partition(arr, cur[0], cur[1]);
            // 注意这里需要判断，
            if (equals[0] > cur[0]) { // 说明存在 < 的区域
                stack.push(new int[] {cur[0], equals[0] - 1});
            }
            if (equals[1] < cur[1]) { // 说明存在 > 的区域
                stack.push(new int[] {equals[1] + 1, cur[1]});
            }
        }
    }

    public static void printArr(int[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = {4, 1, 3, 1, 6, 4, 5, 2, 4};
        //int[] partition = partition(arr, 0, arr.length - 1);
        quickSort(arr);
        printArr(arr);

        int testTime = 100000;
        int maxLength = 1000;
        int maxValue = 1000;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = Code03_Comp.lenRandomValueRandom(maxLength, maxValue);
            int[] arr2 = new int[arr1.length];
            int[] arr3 = new int[arr1.length];
            System.arraycopy(arr1, 0, arr2, 0, arr2.length);
            System.arraycopy(arr1, 0, arr3, 0, arr3.length);
            quickSort(arr1);
            quickSort2(arr2);
            Arrays.sort(arr3);
            //Arrays.sort(arr2);
            if (!compare(arr1, arr3) || !compare(arr2, arr3)) {
                System.out.println("Oops!");
                System.out.println(arr1);
                System.out.println(arr2);
                return;
            }
        }
        System.out.println("测试结束");
    }


    public static boolean compare(int[] arr1, int[] arr2) {
        int L = arr1.length;
        for (int i = 0; i < L; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}
